package com.kevinkk.greedy;

/**
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 */

public class JumpGameII {
    class Solution {
        public int jump(int[] nums) {
            if (nums.length == 1)
                return 0;
            int nextCover = 0;  // nextCover 表示下一跳能到达的范围
            int curCover = 0;   // curCover 表示现在能到达的范围
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                nextCover = Math.max(nextCover, i + nums[i]);
                // 如果到达了当前范围的边界，就需要再跳一步
                if (i >= curCover) {
                    curCover = nextCover;
                    res++;
                    if (curCover >= nums.length - 1)
                        break;
                }
            }

            return res;
        }
    }
}
